The present invention relates to a priority encoder. More specifically, the present invention relates to a priority encoder having increased processing speed for the least significant address bits.
CAM cells are defined as memory cells that are addressed in response to their content, rather than by a physical address within an array. Rows of CAM cells within an array assert or de-assert associated match signals indicating whether or not each CAM cell row matches the data values applied to the CAM cell array. These match signals are provided to a priority encoder that in turn provides the address of the row of matching CAM cells having the highest priority.
FIG. 1 is a block diagram of a conventional 8n-row by 5-column CAM cell memory array 100 and a 3-bit priority encoder 101. The CAM cells are labeled MX, Y, where X is the row of the array, and Y is the column of the array. Thus, the array includes CAM cells M0, 0 to M7, 4. The required number of address signals provided by priority encoder 101 is defined as the base 2 logarithm of the number of rows in CAM cell memory array 100, rounded up.
Each of the CAM cells in array 100 is programmed to store a data value. In the described example, the data value stored in each CAM cell is indicated by either a xe2x80x9c0xe2x80x9d or a xe2x80x9c1xe2x80x9d in brackets. For example, CAM cells M0, 0, M0, 1, M0, 2, M0, 3, and M0, 4 store data values of 1, 1, 1, 1, and 1, respectively. Each row of CAM cells is coupled to a common match line to provide a match signal for the row. For example, CAM cells M0, 0, M0, 1, M0, 2, M0, 3, and M0, 4 are coupled to the common match line that provides the MATCH0 signal.
The array of CAM cells is addressed by providing a data value to each column of CAM cells. Thus, data values D0, D1, D2, D3, and D4 are provided to columns 0, 1, 2, 3, and 4, respectively. Note that complimentary data values D0#, D1#, D2#, D3#, and D4# are also provided to columns 0, 1, 2, 3, and 4, respectively. If the data values stored in a row of the CAM cells match the applied data values D0, D1, D2, D3, and D4, then a match condition occurs. For example, if the data values D0, D1, D2, D3, and D4 are 0, 1, 0, 0, and 0, respectively, then the data values stored in the CAM cells of row 1 match the applied data values. Under these conditions, the MATCH1 signal is high. The high state of the MATCH1 signal is shown by the value xe2x80x9c1xe2x80x9d in brackets. Because the applied data values D0, D1, D2, D3, and D4 also match the data values stored in the CAM cells of rows 3 and 7, the MATCH3 and MATCH7 signals also are high. Because the applied data values D0, D1, D2, D3, and D4 do not match the data values stored in the CAM cells of rows 0, 2, or 4-6, the MATCH0, MATCH2, and MATCH4-MATCH6 signals are pulled low.
Priority encoder 101 receives the MATCH0-MATCH7 signals. Priority encoder 101 is a 3-bit priority encoder because three address signals are required to identify the MATCH0-MATCH7 signals. Each of the MATCH0-MATCH7 signals is received at an address, which is noted beside each match signal. For example, the MATCH1 signal is received at address xe2x80x9c001xe2x80x9d. Priority encoder 101 provides the address of the asserted match signal with the highest priority (lowest address) as the priority address A2-A0. Of the asserted match signals MATCH1, MATCH3, and MATCH7, the MATCH1 signal has the highest priority. Therefore, the address of the MATCH1 signal (i.e., xe2x80x9c001xe2x80x9d) is provided as the priority address A2-A0. Thus, the logic value of priority address bit A2 is xe2x80x9c0xe2x80x9d, of priority address bit A1 is xe2x80x9c0xe2x80x9d, and of priority address bit A0 is xe2x80x9c1xe2x80x9d. Priority encoder 101 asserts the HIT# signal low when at least one of the match signals has a logic high value. This logic low value of the HIT# signal is denoted by a xe2x80x9c0xe2x80x9d in brackets. A logic low value of the HIT# signal means that the priority address A2-A0 is valid.
Conventionally, the bits of the priority address A2-A0 are generated in parallel in response to the MATCH0-MATCH7 signals. Thus, each of the priority address bits A2-A0 is independently generated. As a result, the time taken to provide a valid address from the priority encoder is equal to the maximum time taken to calculate any one of the priority address bits A2-A0.
FIG. 2 is a truth table for 3-bit priority encoder 101 of FIG. 1. Each row is labeled with one of the MATCH0-MATCH7 signals and each column is labeled with one of the priority address bits A2-A0. The table of FIG. 2 shows the priority address associated with each match line. Thus, the priority address of the MATCH3 signal is xe2x80x9c100xe2x80x9d, with the priority address bit A2 equal to xe2x80x9c0xe2x80x9d, the priority address bit A1 equal to xe2x80x9c1xe2x80x9d, and the priority address bit A0 equal to xe2x80x9c1xe2x80x9d. The match signal with the highest priority in this scheme is the match signal with the lowest priority address. Thus, if all of the MATCH0-MATCH7 signals are asserted high, the MATCH0 signal (i.e., the signal at address xe2x80x9c000xe2x80x9d) has priority over the MATCH1-MATCH7 signals (i.e., the signals at addresses xe2x80x9c001xe2x80x9d-xe2x80x9c111xe2x80x9d). In the above example, the MATCH1 signal has the highest priority of the asserted MATCH1, MATCH3, and MATCH7 signals.
FIG. 3 is a schematic diagram of a conventional A0 generator 300. A0 generator 300 includes inverters 301-306, n-channel transistors 307-316 and p-channel transistor 317. A0 generator 300 is used to generate the least significant bit (LSB) (i.e., the A0 signal) of the priority address. A0 generator 300 typically exhibits the largest delay in the generation of priority address bits A2-A0. Each pass transistor 311-316 contributes a resistance (i.e., delay) to the determination of the least significant priority address bit A0. Thus, if the only matching signal is the lowest priority match signal (i.e., the MATCH7 signal), then the total (and worst case) delay in determining the least significant priority address bit A0 is the sum of the delays caused by pass transistors 311-316. If each pass transistor has the same resistance, the total delay for A0 generator 300 is equal to 6 times the delay attributable to one pass transistor, or 6 pass transistor delays.
FIG. 4 is a schematic diagram of another conventional A0 generator 400. A0 generator 400 includes inverters 401-407 and n-channel transistors 408-421. A0 generator 400 also is used to generate the least significant priority address bit A0. Each of pass transistors 415-420 contributes resistance during the determination of priority address bit A0 that results in the worst case delay. If each of pass transistors 415-420 has the same resistance, the worst case delay for A0 generator 400 is equal to 6 times the delay attributable to one pass transistor, or 6 pass transistor delays.
It would therefore be desirable to have a priority encoder that generates the least significant priority address bit A0 more quickly than A0 generators 300 and 400.
Accordingly, the present invention provides an improved method of generating a priority address that includes the steps of: (1) providing a plurality of match signals from a CAM cell array to a priority encoder, (2) generating a most significant address bit of the priority address in response to a first set of the match signals, and (3) generating a least significant address bit of the priority address in response to the most significant address bit and a second set of the match signals.
In one embodiment, the step of generating the least significant address bit is implemented by splitting the determination of the least significant address bit into two separate determinations, and the using the most significant address bit to select the result of one of these two separate determinations.
Using the most significant address bit to help determine the least significant address bit significantly increases the speed of determining the least significant address bit, thereby increasing the overall speed of the priority encoder.
Another embodiment of the present invention includes a priority encoder that generates a priority address in response to a plurality of match signals provided by a CAM cell array. The priority encoder includes a first address generator for generating a most significant priority address bit in response to a first set of match signals, and a second address generator for generating a least significant priority address bit in response to the second set of match signals and the most significant priority address bit.
In one embodiment, the first set of match signals includes the half of the match signals that have the highest priority. The determination of the most significant address bit in response to the first set of match signals is a relatively fast operation, having an insignificant delay. The most significant address bit is provided to the second address generator to control the generation of the least significant address bit.
In one embodiment, the second address generator includes a first circuit, a second circuit, and a selector circuit. The first circuit is configured to generate a first address signal in response to a first subset of the second set of match signals. The second circuit is configured to generate a second address signal in response to a second subset of the second set of match signals. The first circuit performs one half of the determination of the least significant address bit, and the second circuit performs the other half of the determination of the least significant address bit, with the first circuit and the second circuit operating in parallel. The selector circuit routes either the first address signal or the second address signal as the least significant address bit in response to the most significant address bit. Splitting the determination of the least significant address bit into two parallel determinations advantageously minimizes the delay in generating the least significant address bit. As a result, the overall speed of the priority encoder is increased.
The present invention will be more fully understood in view of the following description and drawings.